class Solution:
    def trap(self, height) -> int:
        if len(height) == 0:
            return 0
        left = [0] * len(height)
        right = [0] * len(height)
        left[0] = height[0]
        right[-1] = height[-1]
        for i in range(1, len(height)):
            left[i] = max(left[i - 1], height[i])
        for i in range(len(height) - 2, -1, -1):
            right[i] = max(right[i + 1], height[i])
        # print(left)
        # print(right)
        # print(height)

        r = 0
        for i in range(1, len(height) - 1):
            if height[i] < min(left[i - 1], right[i + 1]):
                r += min(left[i - 1], right[i + 1]) - height[i]
        return r


if __name__ == '__main__':
    so = Solution()
    n = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
    r = so.trap(n)
    print(r)
